#include <stdio.h>
#include <stdlib.h>

// 合并两个已排序的子数组
void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    // 复制数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 合并临时数组回原数组
    i = 0;
    j = 0;
    k = left;

    printf("Merging: [");
    for (int idx = left; idx <= mid; idx++)
    {
        printf("%d", arr[idx]);
        if (idx < mid)
            printf(", ");
    }
    printf("] and [");
    for (int idx = mid + 1; idx <= right; idx++)
    {
        printf("%d", arr[idx]);
        if (idx < right)
            printf(", ");
    }
    printf("]\n");

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制剩余元素
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

    // 打印合并后的结果
    printf("Merged result: [");
    for (int idx = left; idx <= right; idx++)
    {
        printf("%d", arr[idx]);
        if (idx < right)
            printf(", ");
    }
    printf("]\n\n");

    // 释放临时数组
    free(L);
    free(R);
}

// 归并排序主函数
void mergeSort(int arr[], int left, int right)
{
    if (left < right)
    {
        // 找到中间点
        int mid = left + (right - left) / 2;

        printf("Dividing: [");
        for (int i = left; i <= right; i++)
        {
            printf("%d", arr[i]);
            if (i < right)
                printf(", ");
        }
        printf("] into [");
        for (int i = left; i <= mid; i++)
        {
            printf("%d", arr[i]);
            if (i < mid)
                printf(", ");
        }
        printf("] and [");
        for (int i = mid + 1; i <= right; i++)
        {
            printf("%d", arr[i]);
            if (i < right)
                printf(", ");
        }
        printf("]\n\n");

        // 分别排序左右两半
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并已排序的两半
        merge(arr, left, mid, right);
    }
}

int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: "); // 原始数组
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    mergeSort(arr, 0, n - 1); // 调用归并排序函数

    printf("\nSorted array: "); // 排序后的数组
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}